package Demo2;

public class demo6 {
    public void quickSort(int[] array) {
        int end = array.length - 1;
        quickSort(array, 0, end);
    }

    private void quickSortHo(int[] array, int left, int right) {
        // 如果子数组长度为1或更小，则返回（即递归终止条件）
        if (left >= right) {
            return;
        }

        // 查找基准元素的位置，并将数组分成两部分
        int target = findTarget(array, left, right);

        // 对基准元素左边的子数组进行递归排序
        quickSort(array, left, target - 1);

        // 对基准元素右边的子数组进行递归排序
        quickSort(array, target + 1, right);
    }

    public int findTarget(int[] array, int left, int right) {
        // 将最左端的元素作为基准元素
        int temp = array[left];
        int keyi = left; // 保存基准元素的初始位置

        // 开始从数组的两端向中间扫描
        while (left < right) {
            // 从右向左扫描，找到第一个小于基准的元素
            while (left < right && array[right] >= temp) {
                right--;
            }
            // 从左向右扫描，找到第一个大于基准的元素
            while (left < right && array[left] <= temp) {
                left++;
            }
            // 交换左侧找到的大于基准的元素和右侧找到的小于基准的元素
            swap(array, left, right);
        }

        // 将基准元素放置到最终的位置，即左、右指针相遇的位置
        swap(array, keyi, left);

        // 返回基准元素的位置索引
        return left;
    }

    private void swap(int[] array, int pos1, int pos2) {
        // 交换数组中两个位置的元素
        int temp = array[pos1];
        array[pos1] = array[pos2];
        array[pos2] = temp;
    }
}
